import java.util.Arrays;
import java.util.LinkedList;

public class Fibonacci {

    /**
     * {@code Fibonacci}函数
     */
    private static int f(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return f(n - 1) + f(n - 2);
    }

    /**
     * 斐波那契函数{@code 记忆法}
     */
    private static int f_Mem(int[] cache, int n) {
        if (cache[n] != -1) {
            return cache[n];
        }
        cache[n] = f_Mem(cache, n - 1) + f_Mem(cache, n - 2);
        return cache[n];
    }
    public static int f_Mem_test(int n) {
        int[] cache = new int[n + 1];
        Arrays.fill(cache, -1);
        cache[0] = 0;
        cache[1] = 1;
        return f_Mem(cache, n);
    }

    public static int fibonacciQuestion(int n) {
        return f(n);
    }

    public static int rabbitQuestion(int n) {
        return f(n);
    }

    public static int frogStep(int n) {
        return f(n + 1);
    }

    public static void main(String[] args) {
        int n = 40;
        System.out.println("==============我是美美的分割线===============");
        System.out.println("我是原斐波那契");
        Long start1 = System.currentTimeMillis();
        System.out.println(fibonacciQuestion(n));
        Long end1 = System.currentTimeMillis();
        System.out.println("耗时 " + (end1 - start1) + "ms");

        System.out.println("==============我是美美的分割线===============");

        System.out.println("我是兔子问题");
        Long start2 = System.currentTimeMillis();
        System.out.printf("months: %d count: %d %n",n,rabbitQuestion(n));
        Long end2 = System.currentTimeMillis();
        System.out.println("耗时 " + (end2 - start2) + "ms");
        System.out.println("==============我是美美的分割线===============");

        System.out.println("我是青蛙跳楼梯问题");
        Long start3 = System.currentTimeMillis();
        System.out.printf("step: %d count: %d %n",n,frogStep(n));
        Long end3 = System.currentTimeMillis();
        System.out.println("耗时 " + (end3 - start3) + "ms");
        System.out.println("==============我是美美的分割线===============");

        System.out.println("我是记忆法");
        Long start4 = System.currentTimeMillis();
        System.out.println(f_Mem_test(n));
        Long end4 = System.currentTimeMillis();
        System.out.println("耗时 " + (end4 - start4) + "ms");
        System.out.println("==============我是美美的分割线===============");
    }
}
